package demo1;

import java.util.Comparator;
import java.util.PriorityQueue;

public class DynamicPlanningPractise {
    public static void main(String[] args) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1.compareTo(o2);
            }
        });

        PriorityQueue<Integer> queue1 = new PriorityQueue<Integer>(
                (o1,o2)->{return o1.compareTo(o2);});
    }

    /**
     * 下降路径最小和
     * 时间复杂度O（n^2）
     * 空间复杂度O（n^2）
     * */
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        //1 创建dp表
        int[][] dp = new int[n+1][n+2];
        //2 初始化
        for(int i = 1; i <= n; i++)
            dp[i][0] = dp[i][n+1] = Integer.MAX_VALUE;
        //3 填表
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                //4 状态转移方程
                dp[i][j] = Math.min(Math.min(dp[i-1][j-1],dp[i-1][j]),dp[i-1][j+1]) + matrix[i-1][j-1];
        //5 求出最后一排的最小值
        int ret = Integer.MAX_VALUE;
        for(int i = 1; i <= n; i++)
            if(dp[n][i]<ret)
                ret = dp[n][i];
        return ret;
    }

    /**
     * 最小路径和
     * 时间复杂度O（m*n）
     * 空间复杂度O（m*n）
     * */
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        //1 创建dp表
        int[][] dp = new int[m+1][n+1];
        //2 初始化
        for(int i = 0; i <= m; i++)
            dp[i][0] = Integer.MAX_VALUE;
        for(int i = 2; i <= n; i++)
            dp[0][i] = Integer.MAX_VALUE;
        //3 填表
        for(int i = 1; i <= m; i++)
            for(int j = 1; j <= n; j++)
                dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + grid[i-1][j-1];
        return dp[m][n];
    }

    /**
     * 地下城游戏：
     * 时间复杂度O（m*n）
     * 空间复杂度O（m*n）
     * */
    public int calculateMinimumHP(int[][] dungeon) {
        /**
         状态表示：dp[i][j] 表示：以[i][j]位置为起点时，到达终点所需的最小体力值

         状态转移方程：
         情况一：x+dungeon[i][j] >= dp[i][j+1]
         x = dp[i][j+1] - dungeon[i][j]
         情况二：x+dungeon[i][j] >= dp[i+1][j]
         x = dp[i+1][j] - dungeon[i][j]
         为了保证dp[i][j] 是最低健康点数，故得状态转移方程为：
         dp[i][j] = min(dp[i][j+1],dp[i+1][j]) - dungeon[i][j]
         还有一个注意事项：当dp[i][j]的值为1一个负数时，此时说明该节点是一个大血包
         故将其替换为1即可

         初始化：使用虚拟位置法进行初始化

         填表顺序：从下到上，从右到左

         返回值dp[0][0]*/

        int m = dungeon.length, n = dungeon[0].length;
        //1 创建dp表
        int[][] dp = new int[m+1][n+1];
        //2 初始化
        for(int i = 0; i <= n; i++)
            dp[m][i] = Integer.MAX_VALUE;
        for(int i = 0; i <= m-2; i++)
            dp[i][n] = Integer.MAX_VALUE;
        //救完公主后最少得剩下一滴血
        dp[m-1][n] = 1;
        //3 填表
        for(int i = m-1; i >= 0; i--)
            for(int j = n-1; j >= 0; j--)
                dp[i][j] = Math.max((Math.min(dp[i][j+1],dp[i+1][j]) - dungeon[i][j]),1);
        return dp[0][0];
    }
}
